/*
 * @Author: liusheng
 * @Date: 2022-05-15 17:32:27
 * @LastEditors: liusheng
 * @LastEditTime: 2022-05-17 12:14:56
 * @Description: 剑指 Offer II 062. 实现前缀树
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 062. 实现前缀树
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
 

示例：

输入
inputs = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
inputs = [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True
 

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次
 
注意：本题与主站 208 题相同：https://leetcode-cn.com/problems/implement-trie-prefix-tree/ 

通过次数10,050 提交次数13,110
 */

#include "header.h"

/*
ternary tree solution
*/
class Trie {
    struct Node
    {
        //this can be optmize to bool or char,if not use size value
        int val;// val greater than 0 represent there is a string
        char ch; //Node represent ch
        Node * left; //point to charater less than ch
        Node * mid; //point to character equal to ch
        Node * right;//point to character greater than ch
        
        Node(char c)
        {
            val = -1;
            ch = c;
            left = nullptr;
            mid = nullptr;
            right = nullptr;
        }
    };
    
public:
    Trie() {
        root = nullptr;
        n = 0;
    }
    
    void insert(string word) {
        root = put(root,word,0);
    }
    
    bool search(string word) {
        return get(root,word,0) > 0;
    }
    
    bool startsWith(string prefix) {
        return get(root,prefix,0) != -2;
    }
private:
    Node * put(Node * node,const string & key,int pos)
    {
        char ch = key[pos];
        if (!node)
        {
            node = new Node(ch);
        }
        
        if (ch < node->ch)
        {
            node->left = put(node->left,key,pos);
        }
        else if (ch > node->ch)
        {
            node->right = put(node->right,key,pos);
        }
        else //current character equal to node's character,go to next
        {
            if (pos == key.size() - 1)
            {
                //has not been insert
                //else do nothing
                if (node->val < 0)
                {
                    node->val = ++n;
                }
                return node;
            }
            
            //current character equal,go to next position
            node->mid = put(node->mid,key,pos + 1);
        }
        
        return node;
    }
    
    //return value > 0 represent find a string in current tree
    //
    int get(Node * node,const string & key,int pos)
    {
        if (!node)
        {
            return -2;
        }
        
        char ch = key[pos];
        if (ch < node->ch)
        {
            return get(node->left,key,pos);
        }
        else if (ch > node->ch)
        {
            return get(node->right,key,pos);
        }
        else
        {
            if (pos == key.size() - 1)
            {
                //if node->val is greater than 0,there has value,or -1(default value) means find string startwith
                return node->val;
            }
            
            return get(node->mid,key,pos + 1);
        }
    }
private:
    Node * root;
    //if don't need total string size,this can be commented
    int n; //current total size of string
};

/*
字典树 solution
child represent 26 character
*/
class Trie {  
public:
    Trie():children({nullptr}) {
        isEnd = false;
    }
    
    void insert(string word) {
        Trie * node = this;
        for (char ch : word)   
        {
            int charIndex = ch - 'a';
            if (node->children[charIndex] == nullptr)
            {
                node->children[charIndex] = new Trie();
            }
            node = node->children[charIndex];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        Trie * lastNode = getLastNode(word);
        return lastNode && lastNode->isEnd;
    }
    
    bool startsWith(string prefix) {
        return getLastNode(prefix) != nullptr;
    }
private:
    Trie * getLastNode(const string & word)
    {
        Trie * node = this;
        for (char ch: word)
        {
            size_t charIndex = ch - 'a';
            if (node->children[charIndex] == nullptr)
            {
                return nullptr;
            }
            node = node->children[charIndex];
        }
        
        return node;
    }
private:
    array<Trie *,26> children;
    bool isEnd;
};

/*
similar solution as above:
use unordered_map to keep children node
this can reduce space usage,but increase a little time
*/
class Trie {
/**/
public:
    /** Initialize your data structure here. */
    Trie() {
        isEnd = false;
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie * node = this;
        for (char ch : word)
        {
            if (!node->children.count(ch))
            {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie * node = findLastNode(word);
        return node != nullptr && node->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        return findLastNode(prefix) != nullptr;
    }
private:
    Trie * findLastNode(const string & word)
    {
        Trie * node = this;
        for (char ch : word)
        {
            if (!node->children.count(ch))
            {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }
private:
    unordered_map<char,Trie *> children;
    bool isEnd;
};